//Given an m x n grid of characters board and a string word, return true if 
//word exists in the grid. 
//
// The word can be constructed from letters of sequentially adjacent cells, 
//where adjacent cells are horizontally or vertically neighboring. The same letter 
//cell may not be used more than once. 
//
// 
// Example 1: 
//
// 
//Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word =
// "ABCCED"
//Output: true
// 
//
// Example 2: 
//
// 
//Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word =
// "SEE"
//Output: true
// 
//
// Example 3: 
//
// 
//Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word =
// "ABCB"
//Output: false
// 
//
// 
// Constraints: 
//
// 
// m == board.length 
// n = board[i].length 
// 1 <= m, n <= 6 
// 1 <= word.length <= 15 
// board and word consists of only lowercase and uppercase English letters. 
// 
//
// 
// Follow up: Could you use search pruning to make your solution faster with a 
//larger board? 
// Related Topics Array Backtracking Matrix 👍 7905 👎 302


package leetcode.editor.en;

public class _79_WordSearch {
    public static void main(String[] args) {
        Solution solution = new _79_WordSearch().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int[][] direction = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        char[][] board;
        char[] target;
        int row;
        int col;
        boolean[][] visited;

        public boolean exist(char[][] board, String word) {
            row = board.length;
            if (row==0) {
                return false;
            }
            col = board[0].length;
            this.board = board;
            target = word.toCharArray();
            visited = new boolean[row][col];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (dfs(i,j, 0)){
                        return true;
                    }
                }
            }
            return false;
        }

        private boolean dfs(int i, int j, int cur) {
            if (cur==target.length-1){
                return board[i][j] == target[cur];
            }
            if (board[i][j] == target[cur]){
                visited[i][j] = true;
                for (int[] d : direction) {
                    int nexX = i+d[0];
                    int nexY = j+d[1];
                    if (inArea(nexX, nexY) && !visited[nexX][nexY]){
                        if (dfs(nexX, nexY, cur+1)){
                            return true;
                        }
                    }
                }
                visited[i][j] = false;
            }
            return false;
        }

        private boolean inArea(int nexX, int nexY) {
            return 0<=nexX&&nexX<row&&0<=nexY&&nexY<col;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}